/*
 * @lc app=leetcode.cn id=133 lang=golang
 *
 * [133] 克隆图
 */

// @lc code=start
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */

// 可优化
func cloneGraph(node *Node) *Node {
	if node == nil {
		return nil
	}
	isCopy := make(map[*Node][]*Node)
	resCopy := make(map[*Node]*Node)
	routes := []*Node{node}
	for len(routes) != 0 {
		tRoutes := make([]*Node, 0)
		for _, v := range routes {
			if _, ok := isCopy[v]; !ok {
				isCopy[v] = v.Neighbors
				resCopy[v] = &Node{v.Val, []*Node{}}
				tRoutes = append(tRoutes, v.Neighbors...)
			}
		}
		routes = tRoutes
	}
	for k1, v := range isCopy {
		for _, k2 := range v {
			resCopy[k1].Neighbors = append(resCopy[k1].Neighbors, resCopy[k2])
		}
	}
	return resCopy[node]

}

// @lc code=end
